/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void insert(ListNode* pre, ListNode* x)
    {
        x->next=pre->next;
        pre->next=x;
    }
    
    void rearrangedList(ListNode* head) {
        if(!head->next) return;
        
        int n=0;
        ListNode *h1=head, *h2=head, *t;
        while(h1) n++, h1=h1->next; //计算长度
        h1=head;
        for(int i=1; i<(n+1)/2; i++) h1=h1->next;
        h2=h1->next; //h1是前半段链表的最后一个节点 h2是后半链表第一个节点
        t=h2->next;
        h1->next=h2->next=nullptr;
        
        while(t) 
        {
            ListNode* t2=t->next;
            t->next=h2;
            h2=t;
            t=t2;
        }
        h1=head;
        while(h2)
        {
           t=h2->next;
        //   h2->next=h1->next;
        //   h1->next=h2;
        insert(h1, h2);
           h1=h2->next;
           h2=t;
           
        }
    }
};